package reviewAlgorithms.greedyThought;

import java.util.Arrays;

public class ReconstructQueue {
    public static void main(String[] args) {

        int[][] people = {{7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2}};
        System.out.println(Arrays.deepToString(reconstructQueue(people)));
    }
    public static int[][] reconstructQueue(int[][] people) {
        if (people == null || people.length < 1){
            return people;
        }
        Arrays.sort(people, (o1, o2) -> {
            if (o2[0] != o1[0]){
                return o1[0] -o2[0];
            }else {
                return o1[1] - o2[1];
            }
        });
        for (int i = people.length - 1; i >= 0 ; i--) {
            int move = legal(i,people);
            if (move > 0){
                int k = i;
                for (int j = 0; j < move; j++) {
                    int[] temp = people[k];
                    people[k] = people[k + 1];
                    people[k + 1] = temp;
                    k ++;
                }
            }
        }
        return people;
    }

    private static int legal(int i, int[][] people) {
        int count = 0;
        for (int j = 0; j < i ; j++) {
            if (people[j][0] >= people[i][0]){
                count ++;
            }
        }
        return people[i][1] - count;
    }
}
